home *** CD-ROM | disk | FTP | other *** search
/ The Atari Compendium / The Atari Compendium (Toad Computers) (1994).iso / files / internet / other / mail / pathalia.zoo / src / printit.c < prev    next >
Encoding:
C/C++ Source or Header  |  1991-01-12  |  6.7 KB  |  326 lines
  1. /* pathalias -- by steve bellovin, as told to peter honeyman */
  2. #ifndef lint
  3. static char    *sccsid = "@(#)printit.c    9.4 89/02/07";
  4. #endif
  5.  
  6. #include "def.h"
  7.  
  8. /*
  9.  * print the routes by traversing the shortest path tree in preorder.
  10.  * use lots of char bufs -- profiling indicates this costs about 5 kbytes
  11.  */
  12.  
  13. /* exports */
  14. extern void printit();
  15.  
  16. /* imports */
  17. extern int Cflag, Vflag, Dflag, Fflag;
  18. extern node *Home;
  19. extern char *Netchars;
  20. extern void die();
  21. extern int strlen();
  22.  
  23. /* privates */
  24. static link *Ancestor;    /* for -f option */
  25. STATIC void preorder(), setpath(), printhost(), printdomain();
  26. STATIC char *hostpath();
  27. STATIC int printable();
  28.  
  29. /* in practice, even the longest paths are < 100 bytes */
  30. #define PATHSIZE 512
  31.  
  32. void
  33. printit()
  34. {    link *l;
  35.     char pbuf[PATHSIZE];
  36.  
  37.     /* print home */
  38.     if (Cflag)
  39.         printf("%ld\t", (long) Home->n_cost);
  40.     printf("%s\t%%s\n", Home->n_name);
  41.     
  42.     strcpy(pbuf, "%s");
  43.     for (l = Home->n_link; l; l = l->l_next) {
  44.         if (l->l_flag & LTREE) {
  45.             l->l_flag &= ~LTREE;
  46.             Ancestor = l;
  47.             preorder(l, pbuf);
  48.             strcpy(pbuf, "%s");
  49.         }
  50.     }
  51.     fflush(stdout);
  52.     fflush(stderr);
  53. }
  54.  
  55. /*
  56.  * preorder traversal of shortest path tree.
  57.  */
  58. STATIC void
  59. preorder(l, ppath)
  60.     register link *l;
  61.     char *ppath;
  62. {    register node *n;
  63.     node *ncp;        /* circular copy list */
  64.     Cost cost;
  65.     char npath[PATHSIZE];
  66.     short p_dir;        /* DIR bits of parent (for nets) */
  67.     char p_op;        /* net op of parent (for nets) */
  68.  
  69.     setpath(l, ppath, npath);
  70.     n = l->l_to;
  71.     if (printable(n)) {
  72.         if (Fflag)
  73.             cost = Ancestor->l_to->n_cost;
  74.         else
  75.             cost = n->n_cost;
  76.         if (ISADOMAIN(n))
  77.             printdomain(n, npath, cost);
  78.         else if (!(n->n_flag & NNET)) {
  79.             printhost(n, npath, cost);
  80.         }
  81.         n->n_flag |= PRINTED;
  82.         for (ncp = n->n_copy; ncp != n; ncp = ncp->n_copy)
  83.             ncp->n_flag |= PRINTED;
  84.     }
  85.  
  86.     /* prepare routing bits for domain members */
  87.     p_dir = l->l_flag & LDIR;
  88.     p_op = l->l_netop;
  89.  
  90.     /* recursion */
  91.     for (l = n->n_link; l; l = l->l_next) {
  92.         if (!(l->l_flag & LTREE))
  93.             continue;
  94.         /* network member inherits the routing syntax of its gateway */
  95.         if (ISANET(n)) {
  96.             l->l_flag = (l->l_flag & ~LDIR) | p_dir;
  97.             l->l_netop = p_op;
  98.         }
  99.         l->l_flag &= ~LTREE;
  100.         preorder(l, npath);
  101.     }
  102. }
  103.  
  104. STATIC int
  105. printable(n)
  106.     register node *n;
  107. {    node *ncp;
  108.     link *l;
  109.  
  110.     if (n->n_flag & PRINTED)
  111.         return 0;
  112.  
  113.     /* is there a cheaper copy? */
  114.     for (ncp = n->n_copy; n != ncp; ncp = ncp->n_copy) {
  115.         if (!(ncp->n_flag & MAPPED))
  116.             continue;    /* unmapped copy */
  117.  
  118.         if (n->n_cost > ncp->n_cost)
  119.             return 0;    /* cheaper copy */
  120.  
  121.         if (n->n_cost == ncp->n_cost && !(ncp->n_flag & NTERMINAL))
  122.             return 0;    /* synthetic copy */
  123.     }
  124.  
  125.     /* will a domain route suffice? */
  126.     if (Dflag && !ISANET(n) && ISADOMAIN(n->n_parent)) {
  127.         /*
  128.          * are there any interesting links?  a link
  129.          * is interesting if it doesn't point back
  130.          * to the parent, and is not an alias.
  131.          */
  132.  
  133.         /* check n */
  134.         for (l = n->n_link; l; l = l->l_next) {
  135.             if (l->l_to == n->n_parent)
  136.                 continue;
  137.             if (!(l->l_flag & LALIAS))
  138.                 return 1;
  139.         }
  140.  
  141.         /* check copies of n */
  142.         for (ncp = n->n_copy; ncp != n; ncp = ncp->n_copy) {
  143.             for (l = ncp->n_link; l; l = l->l_next) {
  144.                 if (l->l_to == n->n_parent)
  145.                     continue;
  146.                 if (!(l->l_flag & LALIAS))
  147.                     return 1;
  148.             }
  149.         }
  150.  
  151.         /* domain route suffices */
  152.         return 0;
  153.     }
  154.     return 1;
  155. }
  156.  
  157. STATIC void
  158. setpath(l, ppath, npath) 
  159.     link *l;
  160.     register char *ppath, *npath;
  161. {    register node *next, *parent;
  162.     char netchar;
  163.  
  164.     next = l->l_to;
  165.     parent = next->n_parent;
  166.     netchar = NETCHAR(l);
  167.  
  168.     /* for magic @->% conversion */
  169.     if (parent->n_flag & ATSIGN)
  170.         next->n_flag |= ATSIGN;
  171.  
  172.     /*
  173.      * i've noticed that distant gateways to domains frequently get
  174.      * ...!gateway!user@dom.ain wrong.  ...!gateway!user%dom.ain
  175.      * seems to work, so if next is a domain and the parent is
  176.      * not the local host, force a magic %->@ conversion.  in this
  177.      * context, "parent" is the nearest ancestor that is not a net.
  178.      */
  179.     while (ISANET(parent))
  180.         parent = parent->n_parent;
  181.     if (ISADOMAIN(next) && parent != Home)
  182.         next->n_flag |= ATSIGN;
  183.  
  184.     /*
  185.      * special handling for nets (including domains) and aliases.
  186.      * part of the trick is to treat aliases to domains as 0 cost
  187.      * links.  (the author believes they should be declared as such
  188.      * in the input, but the world disagrees).
  189.      */
  190.     if (ISANET(next) || ((l->l_flag & LALIAS) && !ISADOMAIN(parent))) {
  191.         strcpy(npath, ppath);
  192.         return;
  193.     }
  194.         
  195.     if (netchar == '@')
  196.         if (next->n_flag & ATSIGN)
  197.             netchar = '%';    /* shazam?  shaman? */
  198.         else
  199.             next->n_flag |= ATSIGN;
  200.  
  201.     /* remainder should be a sprintf -- foo on '%' as an operator */
  202.     for ( ; (*npath = *ppath) != 0; ppath++) {
  203.         if (*ppath == '%') {
  204.             switch(ppath[1]) {
  205.             case 's':
  206.                 ppath++;
  207.                 npath = hostpath(npath, l, netchar);
  208.                 break;
  209.  
  210.             case '%':
  211.                 *++npath = *++ppath;
  212.                 npath++;
  213.                 break;
  214.  
  215.             default:
  216.                 die("unknown escape in setpath");
  217.                 break;
  218.             }
  219.         } else
  220.             npath++;
  221.     }
  222. }
  223.  
  224. STATIC char *
  225. hostpath(path, l, netchar)
  226.     register char *path;
  227.     register link *l;
  228.     char netchar;
  229. {    register node *prev;
  230.  
  231.     prev = l->l_to->n_parent;
  232.     if (NETDIR(l) == LLEFT) {
  233.         /* host!%s */
  234.         strcpy(path, l->l_to->n_name);
  235.         path += strlen(path);
  236.         while (ISADOMAIN(prev)) {
  237.             strcpy(path, prev->n_name);
  238.             path += strlen(path);
  239.             prev = prev->n_parent;
  240.         }
  241.         *path++ = netchar;
  242.         if (netchar == '%')
  243.             *path++ = '%';
  244.         *path++ = '%';
  245.         *path++ = 's';
  246.     } else {
  247.         /* %s@host */
  248.         *path++ = '%';
  249.         *path++ = 's';
  250.         *path++ = netchar;
  251.         if (netchar == '%')
  252.             *path++ = '%';
  253.         strcpy(path, l->l_to->n_name);
  254.         path += strlen(path);
  255.         while (ISADOMAIN(prev)) {
  256.             strcpy(path, prev->n_name);
  257.             path += strlen(path);
  258.             prev = prev->n_parent;
  259.         }
  260.     }
  261.     return path;
  262. }
  263.  
  264. STATIC void
  265. printhost(n, path, cost)
  266.     register node *n;
  267.     char *path;
  268.     Cost cost;
  269. {
  270.     if (n->n_flag & PRINTED)
  271.         die("printhost called twice");
  272.     n->n_flag |= PRINTED;
  273.     /* skip private hosts */
  274.     if ((n->n_flag & ISPRIVATE) == 0) {
  275.         if (Cflag)
  276.             printf("%ld\t", (long) cost);
  277.         fputs(n->n_name, stdout);
  278.         putchar('\t');
  279.         puts(path);
  280.     }
  281. }
  282.  
  283. STATIC void
  284. printdomain(n, path, cost)
  285.     register node *n;
  286.     char *path;
  287.     Cost cost;
  288. {    node *p;
  289.  
  290.     if (n->n_flag & PRINTED)
  291.         die("printdomain called twice");
  292.     n->n_flag |= PRINTED;
  293.  
  294.     /*
  295.      * print a route for dom.ain if it is a top-level domain, unless
  296.      * it is private.
  297.      *
  298.      * print a route for sub.dom.ain only if all its ancestor dom.ains
  299.      * are private and sub.dom.ain is not private.
  300.      */
  301.     if (!ISADOMAIN(n->n_parent)) {
  302.         /* top-level domain */
  303.         if (n->n_flag & ISPRIVATE) {
  304.             vprintf(stderr, "ignoring private top-level domain %s\n", n->n_name);
  305.             return;
  306.         }
  307.     } else {
  308.         /* subdomain */
  309.         for (p = n->n_parent; ISADOMAIN(p); p = p->n_parent)
  310.             if (!(p->n_flag & ISPRIVATE))
  311.                 return;
  312.         if (n->n_flag & ISPRIVATE)
  313.             return;
  314.     }
  315.  
  316.     /* print it (at last!) */
  317.     if (Cflag)
  318.         printf("%ld\t", (long) cost);
  319.     do {
  320.         fputs(n->n_name, stdout);
  321.         n = n->n_parent;
  322.     } while (ISADOMAIN(n));
  323.     putchar('\t');
  324.     puts(path);
  325. }
  326.